1. Field of the Invention
Methods and apparatuses consistent with the present invention relate to digital signature generation, and in particular, to reducing a degree of complexity of the signature for generating the digital signature and rapidly carrying out the digital signature generation.
2. Description of the Related Art
A digital signature is information generated for validating identification of the signer by the medium of a computer. The digital signature is an electronic document attached to or logically connected to a document message, and is used for validating the signer and representing an approval of the signer about contents of the document message. The digital signature is an electronic substitution for a manual signature or a seal. In general, a public key encryption scheme (i.e., an asymmetrical encryption system) is used for the digital signature.
The digital signature acts to prove the fact that a person who is written as the signer of the digital signature has created the electronic document and the fact that the contents are not forged nor altered in transit. The digital signature also acts to prevent the person from subsequently denying that he has written the contents.
The digital signature has the capability of reducing the risk of information leakage which might occur in an Internet shopping transaction or a cyber financial transaction, so that a fraudulent use or alteration of the personal information can be prevented by utilizing the digital signature.
A representative usage of the digital signature may correspond to a financial transaction such as Internet banking, Internet public affairs service, Internet shopping and so forth, and may extend to international e-commerce, electronic voting and so forth in the future. A public certificate necessary for an Internet banking or an on-line stock trading is a representative digital signature which is issued by a certificate authority designated by the country. The certificate authority manages a public key.
FIG. 1 shows an example of generating a digital signature in the related art. Hereinafter, a method of generating the digital signature according to the related art will be described with reference to FIG. 1. Hereinafter, an apparatus generating the digital signature will be referred to as a digital signature generation unit for simplicity of description.
When a message to be transmitted is generated, the digital signature generation unit generates a digital signature from the generated message. The digital signature generation unit calculates a hash operation value from the generated message using a hash function. The digital signature generation unit generates the digital signature using the calculated hash operation value.
When the hash operation value generated by the digital signature generation unit is represented as eight bits, the hash operation value generated by the digital signature generation unit has values in range of ‘0000 0000’ to ‘1111 1111’. That is, the hash operation value has values from ‘0’ to ‘28−1’. Referring to FIG. 1, n is 28−1. When the hash operation value of the generated message is ‘0000 1111’, it can be represented as ‘15’ in the decimal numeral.
The digital signature generation unit uses, as the digital signature, a value resulting from hashing with a secret key (a).
The hash operation value from the generated message is used to determine the number of times for hashing the secret key in the digital signature generation unit. As described above, the hash operation value of the generated message is ‘15’, so that the digital signature to be delivered has a key value which is hashed fifteen times to generate the public key. That is, the digital signature generation unit sets ‘h2^(8)−1−15(a)’ to the digital signature.
Referring to FIG. 1, a denotes a secret key, and hn(a) is a public key. Accordingly, the hash function is a unidirectional function so that a third party cannot obtain the secret key from the public key.
A digital signature receiving unit receives the message and the digital signature from the digital signature generation unit. The digital signature receiving unit calculates a value by hashing the received message. The digital signature receiving unit then hashes the received digital signature by the number of times corresponding to the calculated value. As described above, if the number corresponding to the calculated value from the message is ‘15’, the digital signature receiving unit hashes the received digital signature fifteen times. When the value resulting from the fifteen hash operations is equal to the public key, the digital signature receiving unit recognizes that the digital signature is not forged nor altered. However, when the value resulting from the fifteen hash operations is not equal to the received public key, the digital signature receiving unit recognizes that the digital signature is forged or altered.
As described with reference to FIG. 1, the digital signature receiving unit hashes the received digital signature by the number of times corresponding to the calculated value. That is, the number corresponding to the calculated value is proportional to the number of hash operations. Accordingly, when the number corresponding to the calculated value is large, the number of hash operations also increases.
When the number corresponding to the calculated value is large, the number of operations carried out in the digital signature receiving unit increases, which in turn causes an increase in time taken for validating the forgery or alteration of the digital signature.
Similar problems occur in the digital signature generation unit. That is, the number corresponding to the value calculated in the digital signature generation unit is in inverse proportion to the number of hash operations. That is, when the number corresponding to the value calculated in the digital signature generation unit is small, the number of hash operations for the secret key increases. Accordingly, the number of operations of the digital signature generation unit increases, which in turn causes an increase in time taken for generating the digital signature.